# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 四数之和转换为三数之和，三数之和转换为二数之和，通过之前的两数之和解决问题
        nums.sort()
        results = []
        self.findNsum(nums, target, 4, [], results)
        return results

    def findNsum(self, nums: List[int], target: int, N: int, tempList: List[int], results: List[List[int]]):
        # 如果数组的长度少于 N 个，或者目标是单数，结束循环
        if len(nums) < N or N < 2:
            return

            # 两数之和
        if N == 2:
            l = 0
            # 每次传入的数组都是过滤过的
            r = len(nums) - 1
            while l < r:
                if nums[l] + nums[r] > target:
                    r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    results.append(tempList + [nums[l] , nums[r]])
                    # 下标推进
                    l += 1
                    r -= 1

                    # 跳过重复的数字(数组已经进行过排序)
                    # 如果当前值等于上一个值，就跳过
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r + 1] == nums[r]:
                        r -= 1
        # 不是两数之和
        else:
            for i in range(0, len(nums)):
                # i == 0 or (i > 0 and nums[i-1] != nums[i] )
                if i == 0 or i > 0 and nums[i - 1] != nums[i]:
                    # 跳过第一个符合目标的值
                    self.findNsum(nums[i + 1:], target - nums[i], N - 1, tempList + [nums[i]], results)
        return

    # Press the green button in the gutter to run the script.


if __name__ == '__main__':
    nums = [1, 0, -1, 0, -2, 2]
    target = 0
    solution = Solution()
    print(solution.fourSum(nums, target))

# See PyCharm help at https://www.jetbrains.com/help/pycharm/
